\relax 
\citation{bresina02}
\citation{Mahootchi2009}
\citation{reservoir}
\citation{feng04,li05}
\citation{lqgc}
\@writefile{toc}{\contentsline {section}{\numberline {1}Introduction}{1}}
\newlabel{Introduction}{{1}{1}}
\newlabel{trans:nonlin}{{1}{2}}
\newlabel{rew:nonlinear}{{2}{2}}
\citation{feng04,li05}
\newlabel{eq:mr_discrete_trans}{{3}{3}}
\newlabel{eq:mr_cont_trans}{{4}{3}}
\newlabel{eq:mr_reward}{{5}{3}}
\newlabel{eq:vfun_rover1}{{6}{3}}
\citation{fomdp}
\@writefile{lof}{\contentsline {figure}{\numberline {1}{\ignorespaces \relax \fontsize  {9}{11}\selectfont  \abovedisplayskip 8\p@ plus2\p@ minus4\p@ \abovedisplayshortskip \z@ plus\p@ \belowdisplayshortskip 4\p@ plus2\p@ minus2\p@ \def \leftmargin \leftmargini \parsep 4.5\p@ plus2\p@ minus\p@ \topsep 9\p@ plus3\p@ minus5\p@ \itemsep 4.5\p@ plus2\p@ minus\p@ {\leftmargin \leftmargini \topsep 4\p@ plus2\p@ minus2\p@ \parsep 2\p@ plus\p@ minus\p@ \itemsep \parsep }\belowdisplayskip \abovedisplayskip Optimal sum of rewards (value) $V^t(x)$ for $b = 0 \tmspace  +\thinmuskip {.1667em} (\mathit  {false})$ for time horizons (i.e., decision stages remaining) $t=0$, $t=1$, and $t=2$ on the continuous action \textsc  {Mars Rover}\ problem. For $x \in [-2,2]$, the rover automatically takes a picture and receives a reward quadratic in $x$. We initialized $V^0(x,b) = R(x,b)$; for $V^1(x)$, the rover achieves non-zero value up to $x = \pm 12$ and for $V^2(x)$, up to $x = \pm 22$.}}{4}}
\newlabel{fig:opt_graph}{{1}{4}}
\@writefile{lof}{\contentsline {figure}{\numberline {2}{\ignorespaces \relax \fontsize  {9}{11}\selectfont  \abovedisplayskip 8\p@ plus2\p@ minus4\p@ \abovedisplayshortskip \z@ plus\p@ \belowdisplayshortskip 4\p@ plus2\p@ minus2\p@ \def \leftmargin \leftmargini \parsep 4.5\p@ plus2\p@ minus\p@ \topsep 9\p@ plus3\p@ minus5\p@ \itemsep 4.5\p@ plus2\p@ minus\p@ {\leftmargin \leftmargini \topsep 4\p@ plus2\p@ minus2\p@ \parsep 2\p@ plus\p@ minus\p@ \itemsep \parsep }\belowdisplayskip \abovedisplayskip Optimal value function $V^1(x)$ for the continuous action \textsc  {Mars Rover}\ problem represented as an extended algebraic decision diagram (XADD). Here the solid lines represent the $\mathit  {true}$ branch for the decision and the dashed lines the $\mathit  {false}$ branch. To evaluate $V^1(x)$ for any state $x$, one simply traverses the diagram in a decision-tree like fashion until a leaf is reached where the non-parenthetical expression provides the \emph  {optimal value} and the parenthetical expression provides the \emph  {optimal policy} ($a = \pi ^{*,1}(x)$) to achieve value $V^1(x)$.}}{4}}
\newlabel{fig:opt_val_pol}{{2}{4}}
\citation{bahar93add}
\citation{spudd}
\citation{penberthy94}
\citation{li05}
\@writefile{toc}{\contentsline {section}{\numberline {2}Discrete and Continuous State-Action MDPs}{5}}
\newlabel{DC-MDP}{{2}{5}}
\@writefile{toc}{\contentsline {subsection}{\numberline {2.1}Factored Representation}{5}}
\newlabel{sec:dcmdps}{{2.1}{5}}
\citation{boutilier99dt}
\citation{dbn}
\newlabel{eq:vfun_def}{{7}{6}}
\citation{feng04,hao09}
\citation{feng04,li05,hao09}
\citation{bellman}
\newlabel{rew:linear}{{8}{7}}
\@writefile{toc}{\contentsline {subsection}{\numberline {2.2}Solution methods}{7}}
\newlabel{sec:soln}{{2.2}{7}}
\newlabel{eq:qfun}{{9}{7}}
\citation{feng04}
\citation{li05}
\citation{hao09}
\citation{feng04}
\citation{penberthy94}
\citation{boyan01}
\citation{phase07}
\citation{kveton06}
\citation{munos02}
\newlabel{eq:vfun}{{10}{8}}
\@writefile{toc}{\contentsline {subsection}{\numberline {2.3}Related Work}{8}}
\citation{lqgc}
\citation{hao09}
\citation{apricodd}
\citation{munos02,kveton06,phase07}
\citation{fomdp}
\citation{fomdp}
\@writefile{toc}{\contentsline {section}{\numberline {3}Symbolic Dynamic Programming}{9}}
\newlabel{SDP}{{3}{9}}
\@writefile{toc}{\contentsline {subsection}{\numberline {3.1}Case Representation and Operations}{9}}
\citation{varelim}
\@writefile{toc}{\contentsline {subsection}{\numberline {3.2}Symbolic Dynamic Programming (SDP)}{11}}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {3.2.1}SVI for Discrete Actions}{11}}
\newlabel{alg:vi}{{1}{12}}
\@writefile{loa}{\contentsline {algocf}{\numberline {1}{\ignorespaces \relax \fontsize  {9}{11}\selectfont  \abovedisplayskip 8\p@ plus2\p@ minus4\p@ \abovedisplayshortskip \z@ plus\p@ \belowdisplayshortskip 4\p@ plus2\p@ minus2\p@ \def \leftmargin \leftmargini \parsep 4.5\p@ plus2\p@ minus\p@ \topsep 9\p@ plus3\p@ minus5\p@ \itemsep 4.5\p@ plus2\p@ minus\p@ {\leftmargin \leftmargini \topsep 4\p@ plus2\p@ minus2\p@ \parsep 2\p@ plus\p@ minus\p@ \itemsep \parsep }\belowdisplayskip \abovedisplayskip \texttt  {VI}(CSA-MDP, $H$) $\DOTSB \relbar \joinrel \rightarrow $ $(V^h,\pi ^{*,h})$ }}{12}}
\newlabel{alg:regress}{{2}{12}}
\@writefile{loa}{\contentsline {algocf}{\numberline {2}{\ignorespaces \relax \fontsize  {9}{11}\selectfont  \abovedisplayskip 8\p@ plus2\p@ minus4\p@ \abovedisplayshortskip \z@ plus\p@ \belowdisplayshortskip 4\p@ plus2\p@ minus2\p@ \def \leftmargin \leftmargini \parsep 4.5\p@ plus2\p@ minus\p@ \topsep 9\p@ plus3\p@ minus5\p@ \itemsep 4.5\p@ plus2\p@ minus\p@ {\leftmargin \leftmargini \topsep 4\p@ plus2\p@ minus2\p@ \parsep 2\p@ plus\p@ minus\p@ \itemsep \parsep }\belowdisplayskip \abovedisplayskip \texttt  {Regress}($V,a,\mathaccentV {vec}17E{y}$) $\DOTSB \relbar \joinrel \rightarrow $ $Q$ }}{12}}
\newlabel{eq:one_int}{{11}{13}}
\newlabel{eq:cond_sub}{{12}{13}}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {3.2.2}SVI for Continuous actions}{14}}
\newlabel{alg:contMax}{{3}{15}}
\@writefile{loa}{\contentsline {algocf}{\numberline {3}{\ignorespaces \relax \fontsize  {9}{11}\selectfont  \abovedisplayskip 8\p@ plus2\p@ minus4\p@ \abovedisplayshortskip \z@ plus\p@ \belowdisplayshortskip 4\p@ plus2\p@ minus2\p@ \def \leftmargin \leftmargini \parsep 4.5\p@ plus2\p@ minus\p@ \topsep 9\p@ plus3\p@ minus5\p@ \itemsep 4.5\p@ plus2\p@ minus\p@ {\leftmargin \leftmargini \topsep 4\p@ plus2\p@ minus2\p@ \parsep 2\p@ plus\p@ minus\p@ \itemsep \parsep }\belowdisplayskip \abovedisplayskip \texttt  {Continuous Maximization}($y$, $f(\mathaccentV {vec}17E{b},\mathaccentV {vec}17E{x},y)$) $\DOTSB \relbar \joinrel \rightarrow (max_{y}f(\mathaccentV {vec}17E{b},\mathaccentV {vec}17E{x},y)$ }}{15}}
\newlabel{eq:casemax_max}{{14}{15}}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {3.2.3}SVI for Mixed action sets}{17}}
\citation{bout96}
\citation{bahar93add}
\@writefile{toc}{\contentsline {section}{\numberline {4}Extended ADDs (XADDs)}{18}}
\newlabel{XADD}{{4}{18}}
\@writefile{toc}{\contentsline {subsection}{\numberline {4.1}Formal Definition and Operations}{19}}
\citation{penberthy94}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {4.1.1}Unary XADD Operations}{23}}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {4.1.2}Binary XADD Operations}{23}}
\newlabel{fig:reorder}{{4}{24}}
\@writefile{loa}{\contentsline {algocf}{\numberline {4}{\ignorespaces {\sc  Reorder}(F) }}{24}}
\@writefile{toc}{\contentsline {subsection}{\numberline {4.2}XADD Algorithms}{24}}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {4.2.1}Reduce Algorithm for XADDs}{24}}
\newlabel{algReduceXADD}{{5}{25}}
\@writefile{loa}{\contentsline {algocf}{\numberline {5}{\ignorespaces {\sc  ReduceXADD}(F) }}{25}}
\newlabel{algGetNode}{{6}{25}}
\@writefile{loa}{\contentsline {algocf}{\numberline {6}{\ignorespaces {\sc  GetNode}($\delimiter "426830A \mathit  {var}, F_h, F_l \delimiter "526930B $) }}{25}}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {4.2.2}Apply Algorithm for binary operations of XADDs}{25}}
\newlabel{algChooseVarBranch}{{7}{26}}
\@writefile{loa}{\contentsline {algocf}{\numberline {7}{\ignorespaces {\sc  ChooseVarBranch}($F_1,F_2$) }}{26}}
\@writefile{lot}{\contentsline {table}{\numberline {1}{\ignorespaces Input case and result for the method \emph  {ComputeResult} for binary operations $\oplus $, $\ominus $ and $\otimes $ for XADDs.}}{26}}
\newlabel{tab:ComputeResultXADD}{{1}{26}}
\newlabel{algApply}{{8}{27}}
\@writefile{loa}{\contentsline {algocf}{\numberline {8}{\ignorespaces {\sc  Apply}($F_1,F_2,\mathit  {op}$) }}{27}}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {4.2.3}Continuous Maximization Algorithm for XADDs}{27}}
\@writefile{lof}{\contentsline {figure}{\numberline {3}{\ignorespaces \relax \fontsize  {9}{11}\selectfont  \abovedisplayskip 8\p@ plus2\p@ minus4\p@ \abovedisplayshortskip \z@ plus\p@ \belowdisplayshortskip 4\p@ plus2\p@ minus2\p@ \def \leftmargin \leftmargini \parsep 4.5\p@ plus2\p@ minus\p@ \topsep 9\p@ plus3\p@ minus5\p@ \itemsep 4.5\p@ plus2\p@ minus\p@ {\leftmargin \leftmargini \topsep 4\p@ plus2\p@ minus2\p@ \parsep 2\p@ plus\p@ minus\p@ \itemsep \parsep }\belowdisplayskip \abovedisplayskip Representing one step of Continuous Maximization algorithm using XADDs. The upper and lower bounds of action $a$ and the root is represented by XADDs and substituted inside the leaf node. The maximum of the upper and lower bound is then represented. The final result takes the maximum of this and the root considering the constraints and independent decisions and also linearizing the decision nodes.}}{28}}
\newlabel{fig:xadd_max}{{3}{28}}
\newlabel{algLinearize}{{9}{29}}
\@writefile{loa}{\contentsline {algocf}{\numberline {9}{\ignorespaces {\sc  ReduceLinearize}(F) }}{29}}
\@writefile{lof}{\contentsline {figure}{\numberline {4}{\ignorespaces \relax \fontsize  {9}{11}\selectfont  \abovedisplayskip 8\p@ plus2\p@ minus4\p@ \abovedisplayshortskip \z@ plus\p@ \belowdisplayshortskip 4\p@ plus2\p@ minus2\p@ \def \leftmargin \leftmargini \parsep 4.5\p@ plus2\p@ minus\p@ \topsep 9\p@ plus3\p@ minus5\p@ \itemsep 4.5\p@ plus2\p@ minus\p@ {\leftmargin \leftmargini \topsep 4\p@ plus2\p@ minus2\p@ \parsep 2\p@ plus\p@ minus\p@ \itemsep \parsep }\belowdisplayskip \abovedisplayskip Using pruning algorithms for inconsistency and redundancy. Top-left figure is reduced to the bottom-left figure using the LP-Solver which recognizes the parent-child relation. The middle figure is reduced to the right-most figure using the SAT-Solver. The paths of each node in the middle graph are demonstrated. These paths along with the child-parent implications in the KB can reduce the redundant node A.}}{29}}
\newlabel{fig:canonical}{{4}{29}}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {4.2.4}Pruning Algorithm for XADDs}{29}}
\newlabel{algPrune}{{10}{30}}
\@writefile{loa}{\contentsline {algocf}{\numberline {10}{\ignorespaces {\sc  PruneInconsistent}(F) }}{30}}
\newlabel{algRedundant}{{11}{31}}
\@writefile{loa}{\contentsline {algocf}{\numberline {11}{\ignorespaces {\sc  PruneRedundancy}(F) }}{31}}
\@writefile{toc}{\contentsline {section}{\numberline {5}Experimental Results}{32}}
\newlabel{results}{{5}{32}}
\@writefile{toc}{\contentsline {subsection}{\numberline {5.1}Domains}{32}}
\@writefile{toc}{\contentsline {paragraph}{\textsc  {Knapsack}}{32}}
\citation{Scarf_Karlin58}
\citation{bitran,wusd10}
\@writefile{toc}{\contentsline {paragraph}{\textsc  {Mars Rover}}{33}}
\@writefile{toc}{\contentsline {paragraph}{\textsc  {Continuous State} \textsc  {Mars Rover Linear}}{33}}
\@writefile{toc}{\contentsline {paragraph}{\textsc  {Inventory Control}}{33}}
\citation{Mahootchi2009,Yeh1985}
\@writefile{toc}{\contentsline {paragraph}{\textsc  {Reservoir Management}}{34}}
\@writefile{lof}{\contentsline {figure}{\numberline {5}{\ignorespaces Space (\# XADD nodes in value function) and time to optimally solve different problem sizes of the two Continuous State \textsc  {Mars Rover}\nobreakspace  {}domains for varying horizon lengths.}}{35}}
\newlabel{fig:all_lin}{{5}{35}}
\@writefile{lof}{\contentsline {figure}{\numberline {6}{\ignorespaces Space (\# XADD nodes in value function) and time for different iterations (horizons) of SDP on Continuous State \textsc  {Mars Rover Linear}\ with 3 image target points. Results shown for SDP with and without XADD infeasible path pruning.}}{35}}
\newlabel{fig:lin3}{{6}{35}}
\@writefile{toc}{\contentsline {subsection}{\numberline {5.2}Results}{35}}
\@writefile{lof}{\contentsline {figure}{\numberline {7}{\ignorespaces \emph  {Optimal} value function (vertical axis) for different domains showing \emph  {non-rectangular} piecewise boundaries. From left to right, \textsc  {Knapsack}\ ($H = \infty $, horizontal axes $x_2$ and $x_1$), \textsc  {Mars Rover Linear}\ with two pictures ($H = 8$, horizontal axes $\mathit  {energy}$ and $\mathit  {time}$), and \textsc  {Mars Rover Nonlinear}\ with one picture ($H = 3$, horizontal axes $y$ and $x$).}}{36}}
\newlabel{fig:plot3D}{{7}{36}}
\@writefile{lof}{\contentsline {figure}{\numberline {8}{\ignorespaces Space (\# XADD nodes in value function) and time for different iterations (horizons) of SDP on Nonlinear Continuous State and Action \textsc  {Mars Rover}\ with 3 different results based on pruning techniques. Results are shown for the XADD with no pruning technique, with only inconsistency checking (LP-solver) and with both the inconsistent and redundancy checking (LP-Solver and SAT-Solver).}}{37}}
\newlabel{fig:roverTS}{{8}{37}}
\@writefile{lof}{\contentsline {figure}{\numberline {9}{\ignorespaces \textsc  {Inventory Control}: space and elapsed time (between current and previous horizon) vs. horizon. }}{37}}
\newlabel{fig:invC}{{9}{37}}
\@writefile{lof}{\contentsline {figure}{\numberline {10}{\ignorespaces \textsc  {Reservoir Management}: {\it  (left)} Policy $\mathit  {no}$-$\mathit  {drain}(e)=\pi ^{2,*}(l_1,l_2)$ showing on the z-axis the elapsed time $e$ that should be executed for $\mathit  {no}$-$\mathit  {drain}$ conditioned on the states; {\it  (middle)} $V^2(l_1,l_2)$; {\it  (right)} $V^9(l_1,l_2)$. }}{37}}
\newlabel{fig:v2plots}{{10}{37}}
\citation{hao09}
\citation{li05}
\citation{apricodd}
\@writefile{toc}{\contentsline {section}{\numberline {6}Concluding Remarks}{38}}
\bibdata{exactsdp}
\bibcite{Scarf_Karlin58}{\BCAY {Arrow, Karlin,\ \BBA\ Scarf}{Arrow et\nobreakspace  {}al.}{1958}}
\bibcite{lqgc}{\BCAY {Athans}{Athans}{1971}}
\bibcite{bahar93add}{\BCAY {Bahar, Frohm, Gaona, Hachtel, Macii, Pardo,\ \BBA\ Somenzi}{Bahar et\nobreakspace  {}al.}{1993}}
\bibcite{bellman}{\BCAY {Bellman}{Bellman}{1957}}
\bibcite{bitran}{\BCAY {Bitran\ \BBA\ Yanasse}{Bitran\ \BBA\ Yanasse}{1982}}
\bibcite{boutilier99dt}{\BCAY {Boutilier, Dean,\ \BBA\ Hanks}{Boutilier et\nobreakspace  {}al.}{1999}}
\bibcite{bout96}{\BCAY {Boutilier, Friedman, Goldszmidt,\ \BBA\ Koller}{Boutilier et\nobreakspace  {}al.}{1996}}
\bibcite{fomdp}{\BCAY {Boutilier, Reiter,\ \BBA\ Price}{Boutilier et\nobreakspace  {}al.}{2001}}
\bibcite{boyan01}{\BCAY {Boyan\ \BBA\ Littman}{Boyan\ \BBA\ Littman}{2001}}
\bibcite{bresina02}{\BCAY {Bresina, Dearden, Meuleau, Ramkrishnan, Smith,\ \BBA\ Washington}{Bresina et\nobreakspace  {}al.}{2002}}
\@writefile{loa}{\addvspace {10\p@ }}
\@writefile{toc}{\contentsline {chapter}{Bibliography}{39}}
\bibcite{dbn}{\BCAY {Dean\ \BBA\ Kanazawa}{Dean\ \BBA\ Kanazawa}{1989}}
\bibcite{feng04}{\BCAY {Feng, Dearden, Meuleau,\ \BBA\ Washington}{Feng et\nobreakspace  {}al.}{2004}}
\bibcite{spudd}{\BCAY {Hoey, St-Aubin, Hu,\ \BBA\ Boutilier}{Hoey et\nobreakspace  {}al.}{1999}}
\bibcite{kveton06}{\BCAY {Kveton, Hauskrecht,\ \BBA\ Guestrin}{Kveton et\nobreakspace  {}al.}{2006}}
\bibcite{reservoir}{\BCAY {Lamond\ \BBA\ Boukhtouta}{Lamond\ \BBA\ Boukhtouta}{2002}}
\bibcite{li05}{\BCAY {Li\ \BBA\ Littman}{Li\ \BBA\ Littman}{2005}}
\bibcite{Mahootchi2009}{\BCAY {Mahootchi}{Mahootchi}{2009}}
\bibcite{phase07}{\BCAY {Marecki, Koenig,\ \BBA\ Tambe}{Marecki et\nobreakspace  {}al.}{2007}}
\bibcite{hao09}{\BCAY {Meuleau, Benazera, Brafman, Hansen,\ \BBA\ Mausam}{Meuleau et\nobreakspace  {}al.}{2009}}
\bibcite{penberthy94}{\BCAY {Penberthy\ \BBA\ Weld}{Penberthy\ \BBA\ Weld}{1994}}
\bibcite{munos02}{\BCAY {Remi\nobreakspace  {}Munos}{Remi\nobreakspace  {}Munos}{2002}}
\bibcite{apricodd}{\BCAY {St-Aubin, Hoey,\ \BBA\ Boutilier}{St-Aubin et\nobreakspace  {}al.}{2000}}
\bibcite{wusd10}{\BCAY {Wu, Shi,\ \BBA\ Duffie}{Wu et\nobreakspace  {}al.}{2010}}
\bibcite{Yeh1985}{\BCAY {Yeh}{Yeh}{1985}}
\bibcite{varelim}{\BCAY {Zhang\ \BBA\ Poole}{Zhang\ \BBA\ Poole}{1996}}
\bibstyle{theapa}
